Free probability and combinatorics

ICM 2002 • Vol. Ill • 1-3

Free Probability and Combinatorics

p. Biane*

Abstract

A combinatorial approach to free probability theory has been developped
by Roland Speicher, based on the notion of noncrossing cumulants, a free
analogue of the classical theory of cumulants in probability theory. We review
this theory, and explain the connections between free probability theory and
random matrices. We relate noncrossing cumulants to classical cumulants and
also to characters of large symmetric groups. Finally we give applications to
the asymptotics of representations of symmetric groups, specifically to the
Littlewood-Richardson rule.

2000 Mathematics Subject Classification: 46L54, 05E10, 60B15.
Keywords and Phrases: Free probability, Symmetric group, Noncrossing
partitions.

1. Introduction

Free probability has been introduced by D. Voiculescu [21] as a means of study-
ing the group von Neumann algebras of free groups, using probabilistic techniques.
His theory has become very successful when he discovered a deep relation with
the theory of random matrices, and solved some old questions in operator algebra,
see U, [7|, [21] for an overview. A purely combinatorial approach to Voiculescu's
definition of freeness has been given by R. Speicher HO], building on G. C.
Rota's approach to classical probability. It is based on the notion of non-
crossing partitions, also known as "planar diagrams" in quantum field theory, and
provides unifying concepts for many computations in free probability. Noncrossing
partitions turn out to be connected with the geometry of the symmetric group, and
this leads to some new understanding of the asymptotic behaviour of the characters
and representations of large symmetric groups. Our aim is to survey these results,
we shall start with the basic definition of freeness, then explain its connection to
random matrix theory. In the third section we review Speicher 's theory. In the
fourth section we show how noncrossing cumulants arise naturally in connection

* Departement de Mathematiques et Applications, Ecole Normale Superieure, 45 rue d'UIm
75005 Paris, France. E-mail: Philippe.Biane@ens.fr

766

P. Biane

with classical cumulants associated with random matrices, and with characters of
symmetric groups. Finally in section 5 we explain the asymptotic behaviour of
representations of symmetric groups in terms of free probability concepts.

2. Freeness and random matrices

The usual framework for free probability is a von Neumann algebra A, equipped

with a faithful, tracial, normal state t. To any self-adjoint element X E A one can
associate its distribution, the probability measure on the real line, uniquely deter-
mined by the identity t(X") = J^x'^^{dx) for all n > 1. This makes it natural to
think of the elements of A as noncommutative random variables, and of r as an ex-
pectation map, and one usually calls noncommutative probability space such a pair
{A,t). Although a great deal of the theory, especially the combinatorial side, can
be developped in a purely algebraic way, assuming only that A is a complex algebra
with unit, and r a complex linear functional, we shall stick to the von Neumann
framework in the present exposition.

Given {A, r), one considers a family {Ai; i E 1} oi von Neumann subalgebras.
This family is called a free family if the following holds: for any fc > 1 and /c-tuple
ai, . . . ,ak & A such that

• each ttj belongs to some algebra A^. , with ii ^ 12, 12 ■ ■ ■ , ik-i 7^ «fej

• T{aj) = for all j,

one has T{a\ . . . a^) = 0.

Moreover, a family of elements of A is called free if the von Neumann al-
gebras each of them generates form a free family. Freeness is a noncommutative
notion analogous to the independence of a-fields in probability theory, but which
incorporates also the notion of algebraic independence.

Observe that if ai and 02 are free elements in {A,t), and one defines the
centered elements dj = — r(aj)l then one can conpute

T(aia2) = T(aia2) + T(ai)T(a2) = T(ai)r(a2)

where the freeness condition has been used to get T{a\a2) = 0. Actually, if {Af, i e
/} is a free family, it is not dificult to see that one can compute the value of r on
any product of the form oi . . . a^, where each aj belongs to some of the A^ 's, in
terms of the quantities T{aj-^ . . ) where all the elements a^^, . . . , Oj, belong to
the same subalgebra. This implies that the value of r on the algebra generated
by the family {Ai;i £ 1} is completely determined by the restrictions of r to
each of these subalgebras. However the problem of finding an explicit formula is
nontrivial, and this is where combinatorics comes in. We shall describe Spcicher's
theory of noncrossing cumulants, which solves this problem, in the next section, but
before that we explain how free probability is relevant to understand large random
matrices.

Consider n random N x N matrices X['^\...,xi^\ of the form

(2.1)

Free Probability and Combinatorics

767

where D^- ;j = 1, . . . ,n are diagonal, hermitian, nonrandom matrices and Uj are
independent unitary random matrices, each distributed with the Haar measure on
the unitary group 'U{N). In other words we have fixed the spectra of the
but their eigenvectors are chosen at random. The n-tuple x[^\ . . . , xi^'^ can
be recovered, up to a global unitary conjugation X-^^ i— > UX^^^U*, (where U
does not depend on i), from its mixed moments, i.e. the set of complex numbers
iTr(xff ^ . . . X^P) where h, . . . ik are arbitrary sequences of indices in {1, . . . , n}.

In particular the spectrum of any noncommutative polynomial of the X^'^'^ can be
recovered from these data. A most remarkable fact is that if we assume that the
individual moments -^Tr((x|^-')'^) converge as N tends to infinity, then the mixed

moments jfTr{x[^^ . . . xl'^^) converge in probability, and their limit is obtained
by the prescriptions of free probability.

Theorem 1. Let (j4,t) be a noncommutative probability space with free self-
adjoint elements Xi,...,X„, satisfying t{X^) = limN^oc jiTr{{X^^'^)''), for all

i and k, then, in probability, j^Tr{x\^\ . . x\^^) ^^v^oo "^i^i-^ ...Xi^), for all
ii, ...,ik.

This striking result was first proved by D. Voiculescu [23], and has lead to the
resolution of many open problems about von Neumann algebras, upon which we
shall not touch here.

3. Noncrossing partitions and cumulants

A partition of the set {1, . . .,n} is said to have a crossing if there exists a
quadruple (i,j, k, I), with l<i<j<k<l<n, such that i and k belong to some
class of the partition and j and I belong to another class. If a partition has no
crossing, it is called noncrossing. The set of all noncrossing partitions of {1, . . . , n}
is denoted by NC{n). It is a lattice for the refinement order, which seems to have
been first systematically investigated in [111] .

Let {A, t) be a non-commutative probability space, then we shall define a
family i?^"^ of n- multilinear forms on A, for n > 1, by the following formula

T(ai...a„)= ^ i?[7r](ai, . . . ,a„). (3.1)

TreNC(n)

Here, for vr e NC{n), one has defined

i?[7r](ai,...,a„) = [] i?(l^l)(ay)

where ay = (oji, • ■ • ,aj^.) if = {ji, . . . , j^} is a class of the partition tt, with
ji < 32 < • ■ • < jk and \V\ = fc is the number of elements of V. In particular
R[ln] = -R^"-* if In is the partition with only one class. Thus one has, for n = 3,

T{aia2a3) = R^^^ai, 02, a^) + R^^'^ (01,02) R^^Has) + R^-^^ai, 03) R^^Ha2)

768

P. Biane

Observe that

r(ai . . . a„ „) + terms involving for k < n

so that the i?*^"^ are weh defined by H3.1() and can be computed by induction on ?i.
They are cahed the noncrossing (or sometimes free) cumulant functionals on A.
The formula H^.tfl can be inverted to yield

i?("^(ai, . . . ,a„) = Moe6([7r, l„])r[7r](ai,...,o„).

7reNC{n)

Here r[7r](ai, . . . , a„) = IlyGir '''i^ji ■ ■ ■ '^jk) where V = {ji, . . . ,jk\ are the classes
of TT, and Moeb is the Mobius function of the lattice NC{n), see [201 ■
For example, one has

i?(i)(ai) = T(ai); i?(2)(ai,a2) = T{aia2) - T(ai)T(a2);

i?(^)(ai, 02, as) = T(aia2a3) - T(ai)T(a2a3) - T(a2)r(aia3)
-r(a3)T(aia2) + 2T(ai)T(a2)T(a3).

Note that when the lattice of all partitions is used instead of noncrossing partitions,
then one gets the usual family of cumulants (see Rota 5H|)i with another Mobius
function.

The connection between noncrossing cumulants and freeness is the following
result from section 4 of |19|.

Theorem 2. Let {Ai;i Cz 1} be a free family of subalgebras of {A,t), and
oi, . . . , a„ £ A be such that aj belongs to some Ai. for each j G {1, 2, . . . , rt}. Then
one has R^^^ai, . . . , a„) = if there exists some j and k with ij ^ i^.

This result leads to an explicit expression for T(ai . . . a„), where ai, . . . ,
is an arbitrary sequence in A, such that each Oj belongs to one of the algebras
Ai\i I. By Theorem 2, in the right hand side of the terms corresponding

to partitions tt having a class containing two elements j, k such that Oj and
belong to distinct algebras give a zero contribution. Thus we have to sum over
partitions in which all j' s belonging to a certain block of the partition are such
that aj belongs to the same algebra. Since we can express noncrossing cumulants
in terms of moments we get the formula for T(ai . . . a„) in terms of the restrictions
of r to each of the subalgebras Ai. Noncrossing cumulants are a powerful tool
for making computations in free probability, see jjl], ^21) El' ffH|j for some
applications. We give a simple illustration below.

Let Xi and X2 be two self-adjoint elements which are free, then the distri-
bution of Xi + X2, depends only on the distributions of Xi and X2 and can be
computed as follows. Let i?(")(Xi, . . . ,Xi) and i?("H^2, . . . , X2), for n > 1, be the
noncrossing cumulants of Xi and X2, then one can expand {Xi+ X2, . . . , Xi +
X2) by multilinearity as ,- i?'-"^(Xij^, . . . ,Xi„) where the sum is over all se-

quences of 1 and 2. By Theorem 2, all terms vanish except R'^"'\Xi, . . . ,Xi) and
i?(")(X2, . . . , X2). It follows that

i?(")(Xi + ^2, . . . ,Xi + X2) = i?(")(Xi, . . . ,Xi) + i?(")(^2, ... ,^2)

Free Probability and Combinatorics

769

allowing the computation of the moments of Xi + X2, hence its distribution, in
terms of the distributions of Xi and X2. It remains to give a compact form to the
relation between moments and noncrossing cumulants. For any self- adjoint element
X with distribution fi, let

be its Cauchy transform, and let

^ 00

K{z) = - + Vi?fez'=
z ^-^

k=0

be the inverse series for composition.
Theorem 3. [E]

One has Rk = i?'''' iX,...,X) for all k.

The operation which associates to the two distributions of Xi and X2 the
distribution of their sum is called the free convolution of measures on the real line,
and was introduced by D. Voiculescu, who first considered the coefficients Rk and
proved the formula for the free convolution of two measures, using very different
methods P^ .

Combining theorems 1 and 2, given two large random matrices of known spec-
tra one can predict the spectral distribution of their sum, with a good accuracy
and probability close to 1. It is illuminating to look at the following example. The
histogram below is made of the 800 eigenvalues of a random matrix of the form
Hi + 112 where Hi and 112 sue two orthogonal projections onto some random sub-
paces of dimension 400 in 0*"°, chosen independently. The curve y = — 7^2

ttW x(2—x)

which corresponds to the large limit predicted by free probability has been drawn.

0*x

0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

770

P. Biane

4. Noncrossing cumulants, random matrices and
characters of symmetric groups

Besides free probability theory, noncrossing partitions appear in several areas
of mathematics. We indicate some relevant connections. The first is with the
theory of map enumeration initiated by investigations of theoretical physicists in
two-dimensional quantum field theory. The noncrossing partitions appear there
under the guise of planar diagrams, the Feynman diagrams which dominate the
matrix integrals in the large N limit. This is of course related to the fact that large
matrices model free probability. We shall not discuss this further here, but refer to
for an accessible introduction. Another place where noncrossing partitions play
a role, which is closely related to the preceding, is the geometry of the symmetric
group, more precisely of its Cayley graph. Consider the (unoriented) graph whose
vertex set is the symmetric group E„, and such that {(Ti, (T2} is an edge if and only
if ai^a2 is a transposition, i.e. this is the Cayley graph of S„ with respect to the
generating set of all transpositions. The distance on the graph is given by

d{(Ti, (72) — n ~ number of orbits of ai^(72 '■= |ctj~^(T2|.

The lattice of noncrossing partitions can be imbedded in S„ in the following way
|10|. given a noncrossing partition of {1, . . . , n}, its image is the permutation a such
that (T{i) is the element in the same class as i, which follows i in the cyclic order
12. ..71. One can check ^ that the image of NC{n) is the set of all permutations
satisfying |cr| + Icr^^cj — |c| where c is the cyclic permutation c{i) — i + 1 mod{n), in
other words, this set consists of all permutations which lie on a geodesic from the
identity to c in the Cayley graph. These facts are at the heart of the connections
between free probability, random matrices and symmetric groups. As an illustration
we shall see how free cumulants arise from asymptotics of both random matrix
theory and symmetric group representation theory.

Recall that cumulants (also called semi-invariants, see e.g. 17 ) of a random
variable X with moments of all orders, are the coefficients in the Taylor expansion
of the logarithm of its characteristic function, i.e.

00

logi?[e**^]= V(zt)

n=0

We shall consider random variables of the following form y(^) = NX{ -^^ where
X(N) ^ UD^^)U* is a random matrix chosen as in (EH) and X[^^ is its upper left
coefficient. Assume now that the moments of X^^' converge

for some probability measure fi on R, with noncrossing cumulants RnifJ-), then one
has

hm i^C„(rW) = ii?„(M).

Free Probability and Combinatorics

771

This was first observed by P. Zinn- Justin a proof using representation theory
has been found by B. Collins [HI-

We have related noncrossing cumulants to usual cumulants via random matrix
theory, we shall see that that noncrossing cumulants are also useful in evaluating
characters of symmetric groups. The precise relation however is not obvious at first
sight.

Let us recall a few facts about irreducible representations of symmetric groups.
It is well known that they can be parametrized by Young diagrams. In the following
it will be convenient to represent a Young diagram by a function w : R — > R such
that uj{x) = |x| for |x| large enough, and w is a piecewise affine function, with slopes
±1, see the following picture which shows the Young diagram corresponding to the
partition 8 = 3 + 2 + 2 + 1.

xi yi X2 y2 2/3 xa.

Alternatively we can encode the Young diagram using the local minima and
local maxima of the function uj, denoted hy xi, . . . ,Xk and yi, . . . , yu-i respectively,
which form two interlacing sequences of integers. These are (-3,-1,2,4) and (-2,1,3)
respectively in the above picture. Associated with the Young diagram there is a
unique probability measure m^^ on the real line, such that

/ —^mJdx) = ~ foj. all z e C \ R.

This probability measure is supported by the set {a;i,...,Xfc} and is called the
transition measure of the diagram, see 0. Let a denote the conjugacy class in S„
of a permutation with k2 cycles of length 2, ^3 of length 3, etc.. Here ^2,^3,...
are fixed while we let n — > 00. Denote by Xuj the normalized character of S„
associated with the Young diagram oj, then the following asymptotic evaluation
holds uniformly on the set of A-balanced Young diagrams, i.e. those whose longest
row and longest column are less that A^/n (where A is some constant > 0),

00

X^(0 = n + 0(n-i-l-l/2). (4.1)

Note that Rk is scaled by A*^ if we scale the diagram by a factor A, therefore the
first term in the right hand side is of order 0(riSj(J+i)''j/2-Ep'=j ) ^ 0(n"l'^l/2),

772

P. Biane

this gives the order of magnitude of the character of a fixed conjugacy group for an
^-balanced diagram.

In [2j a proof of H4.1|l has been given, using in an essential way the Jucys-
Murphy operators. Another proof, leading to an exact formula for characters of
cycles due to S. Kerov 0, was shown to me later by A. Okounkov ^Sj, see H].

5. Representations of large symmetric groups

The asymptotic formula (|4.1|) shows in particular that irreducible characters of
symmetric groups become asymptotically multiplicative i.e. for permutations with
disjoint supports cti and 02, one has

Xu{<Ji<J2) = X^{<yi)xM + 0(n-i-l'^i^^l/2) (5.1)

uniformly on A-balanced diagrams. Conversely, given a central, normalized, positive
definite function on E„, a factorization property such as H5.1|l implies that the
positive function is essentially an irreducible character [3]. More precisely, recall
that a central normalized positive definite function i]j on S„ is a convex combination
of normalized characters, and as such it defines a probability measure on the set
of Young diagrams. For any e,5 > 0, for all n large enough, if an approximate
factorization such as (|5.1(l holds for -0, then there exists a curve lo, such that the
measure on Young diagrams associated with "0 puts a mass larger than 1 — (5 on
Young diagrams which lie in a neighbourhood of this curve, of width e^/n. Therefore
one can say that condition l|5.1() on a positive definite function implies that the
representation associated with this function is approximately isotypical, i.e. almost
all Young diagrams occuring in the decomposition have a shape close to a certain
definite curve.

Using this fact it is possible to understand the asymptotic behaviour of several
operations in representation theory. Consider for example the operation of induc-
tion. One starts with two irreducible representations of symmetric groups , ,
corresponding to two Young diagrams uji and uj2 ■ One can then induce the product
representation loi (E)uj2 of E„j x I]„2 to I]„j+„2 . This new representation is reducible
and the multiplicities of irreducible representations can be computed using a com-
binatorial device, the Littlewood-Richardson rule. This rule however gives little
light on the asymptotic behaviour of the multiplicities. Using the factorization-
concentration result, one can prove that when ni and 712 are very large, but of
the same order of magnitude, then there exists a curve, which depends on uji and
UJ2 , and such that the typical Young diagram occuring in the decomposition of the
induced representation, is close to this curve. As we saw in section 4, one can asso-
ciate a probability measure on the real line to any Young diagram. The description
of the typical shape of Young diagram which occurs in the decomposition of the
induced representation is easier if we use this correspondance between probability
measures and Young diagrams, indeed the probability measure associated with the
shape of the typical Young diagram corresponds to the free convolution of the two
probability measures [2]-

Free Probability and Combinatorics

773

There are analogous results for the restriction of representations from large
symmetric groups to smaller ones. There the corresponding operation on probability
measure is called the free compression, it corresponds at the level of the large matrix
approximation, to taking a random matrix with prescribed eigenvalue distribution,
as in section 2, and extracting a square submatrix. Finally there are also results for
Kronecker tensor products of representations. Here a central role is played by the
well known Kerov-Vershik limit shape, whose associated probability measure is the
semi-circle distribution with density ^v4 — on the interval [—2,2], see

References

[I] p. Biane, Some properties of crossings and partitions. Discrete Math. 175
(1997), no. 1-3, 41-53.

[2] P. Biane, Representations of symmetric groups and free probability. Adv. Math.
138 (1998), no. 1, 126-181.

[3] P. Biane, Approximate factorization and concentration for characters of sym-
metric groups. Internat. Math. Res. Notices no. 4 (2001), 179-192.

[4] P. Biane, Entropie libre et algebres d'operateurs. Seminaire Bourhaki Expose
889, Juin 2001.

[5] P. Biane, Free cumulants and characters of symmetric groups. Preprint, 2001.
[6] B. Collins, Moments and cumulants of polynomial random variables on unitary

groups Preprint, 2002.
[7] L. M. Ge, these Proceedings.

[8] S. V. Kerov, Transition probabilities of continual Young diagrams and the

Markov moment problem Fund. Anal. Appl. 27 (1993), 104-117.
[9] S.Kerov, talk at IHP, January 2000.

[10] G. Kreweras, Sur les partitions non croiscs d'un cycle. Discrete Math. 1 (1972),
no. 4, 333-350.

[II] A. Nica, R. Speicher, Commutators of free random variables, Duke Math. J.
92 (1998), no. 3, 553-592.

[12] A. Nica, R. Speicher, On the multiplication of free A^-tuples of noncommutative
random variables, Amer. J. Math. 118 (1996), no. 4, 799-837.

[13] A. Nica, R Speicher, i?-diagonal pairs — a common approach to Haar unitaries
and circular elements. Free probability theory (Waterloo, ON, 1995), 149-188,
Fields Inst. Commun., 12, Amer. Math. Soc, Providence, RI, 1997.

[14] A. Nica, D. Shlyakhtcnko, R. Speicher, i?-diagonal elements and freeness with
amalgamation. Canad. J. Math. 53 (2001), no. 2, 355-381.

[15] A. Okounkov, private communication.

[16] G.-C. Rota, On the foundations of combinatorial theory. I. Theory of Mbius
functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964) 340-368.

[17] A. N. Shiryaev, Probability Graduate texts in Mathematics 95, Springer, 1991.

[18] P. Sniady, R. Speicher, Continuous family of invariant subspaces for i?-diagonal
operators. Invent. Math., 146 (2001), no. 2, 329-363.

[19] R. Speicher, Multiplicative functions on the lattice of noncrossing partitions
and free convolution. Math. Ann., 298 (1994), no. 4, 611-628.

774

P. Biane

[20] R. Spcichcr, Combinatorial theory of the free product with amalgamation and
operator-valued free probability theory, Mem. Amer. Math. Soc. 132 (1998), no.
627.

[21] D. Voiculcscu, Symmetries of some reduced free product C*-algebras. Operator
algebras and their connections with topology and ergodic theory (Bu§teni, 1983),
Lecture Notes in Math., 1132: 556-588, Springer, Berlin-New York, 1985.

[22] D. Voiculcscu, Addition of non-commuting random variables, J. Operator
Theory 18 (1987) 223-235

[23] D. Voiculescu, Limit laws for random matrices and free products. Inv. Math.
104,(1983) 201-220.

[24] D. Voiculescu, Free probability theory: random matrices and von Neumann
algebras. Proceedings of the International Congress of Mathematicians. Vol. 1,
2 (Zrich, 1994), 227 241, Birkhuscr, Basel, 1995.

[25] P. Zinn-Justin, Universality of correlation functions of Hermitian random ma-
trices in an external field. Comm. Math. Phys. 194 (1998), no. 3, 631-650.

[26] A. Zvonkin, Matrix integrals and map enumeration: an accessible introduction.
Math. Comput. Modelling 26 (1997), no. 8-10, 281-304.